package jjn.carl.binary_tree;

import commons.BinaryTreeHelper;
import commons.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jjn
 * @since 2023/7/18 00:30
 */
public class LeetCode98 {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
    
    public static void main(String[] args) {
        List<Integer> input = new ArrayList<>();
        input.addAll(List.of(5, 4, 6));
        input.add(null);
        input.add(null);
        input.addAll(List.of(3, 7));
        TreeNode node = BinaryTreeHelper.buildTree(input);
        boolean validBST = new LeetCode98().isValidBST(node);
        System.out.println("validBST = " + validBST);
    }
}
